第七章 图                                                             

一、单选题

（    ）1. 在一个图中，所有顶点的度数之和等于图的边数的      倍。
             A．1/2            B.  1             C.  2             D.  4
（     ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的     倍。
             A．1/2            B.  1             C.  2             D.  4
（     ）3. 有8个结点的无向连通图最少有      条边。
             A．5               B.  6             C.  7             D.  8
（     ）4. 有8个结点的有向完全图有      条边。
             A．14             B.  28           C.  56           D.  112
（     ）5. 已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是
             A．0 1 3 2        B.  0 2 3 1     C.  0 3 2 1        D.  0 1 2 3

二、填空题

1. 图有           、         等存储结构，遍历图有                 、                   等方法。
2. 图的深度优先遍历序列             惟一的。

三、简答题

1. 已知如图所示的有向图，请给出该图的:

(1)每个顶点的入/出度； (2)邻接矩阵； (3)邻接表； (4)逆邻接表。

顶点 1 2 3 4 5 6 入度             出度

2. 请对下图的无向带权图：

(1)写出它的邻接矩阵，并按普里姆算法求其最小生成树；

(2)写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

四、给定下列网G:

1. 试着找出网G的最小生成树，画出其逻辑结构图；
2. 用两种不同的表示法画出网G的存储结构图；
3. 用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。